package basis.netease.easy.废弃;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * 7-20 滑动窗口最大值
 * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
 * 返回 滑动窗口中的最大值 。
 * 注：k小于len(nums)
 * 输入格式:
 * 整数数组nums，以及滑动窗口大小k
 * 第一行为nums，以空格分隔
 * 第二行为k
 * 输出格式:
 * 一行整数，包含每个窗口中的最大值，以空格分隔
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 1 3 -1 -3 5 3 6 7
 * 3
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 3 3 5 5 6 7
 * 解释：
 * 步骤	滑动窗口的位置	最大值
 * 0	[1 3 -1] -3 5 3 6 7	3
 * 1	1 [3 -1 -3] 5 3 6 7	3
 * 2	1 3 [-1 -3 5] 3 6 7	5
 * 3	1 3 -1 [-3 5 3] 6 7	5
 * 4	1 3 -1 -3 [5 3 6] 7	6
 * 5	1 3 -1 -3 5 [3 6 7]	7
 */
public class Main_20 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        int k = scanner.nextInt();
        int[] result = maxSlidingWindow(nums, k);
        StringBuilder sb = new StringBuilder();
        for (int val : result) {
            sb.append(val + " ");
        }
        System.out.println(sb.substring(0, sb.length() - 1));
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        LinkedList<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            // 清除队列中所有小于当前元素的旧元素，保证元素按照从大到小排列
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }
            // 添加当前元素的索引
            deque.addLast(i);
            // 如果队列头部的元素已经超出窗口范围，移除它，保证队列元素均在窗口范围内
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }
            // 当窗口达到k大小时，记录最大值，用于输出结果
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }

}
